Có hai truyền thuyết về việc xây ngôi chùa này. Truyền thuyết thứ nhất là chùa trước kia được dựng lên để thờ một bà cụ bán hàng không rõ tên tuổi. Bà cụ thường bán nước chè, đậu nành cho các học trò Trường Quốc Tử Giám. Lại có tư liệu nói thêm là chùa dựng và đầu triều Lê, thế kỷ XV trên nền quán hàng nước của cụ già ấy và có lần vua Lê Thánh Tông (l460-1497) đến thăm Quốc Tử Giám đã ghé vào vãn cảnh chùa.

Truyền thuyết thứ hai gắn liền với một bối cảnh tình thơ đầy lãng mạn. Ấy là từ đầu thế kỷ XIII, vua nhà Lý đã cho dựng ngôi chùa này. Đến đời nhà Trần thì chùa đổi tên là Tiên Phúc vì theo lời đồn đại trong dân gian, thỉnh thoảng người ta vẫn thấy có nàng tiên xuất hiện thướt tha trước sân chùa. Khi vua Lê Thánh Tông đến chùa ngắm cảnh thì bỗng từ trên gác chuông thấy hiện ra một người con gái đẹp ngâm nga mấy vần thơ:

Nhà vua đã cùng nàng tiên xướng họa, sau đó, nàng tiên biến mất tại đình Quảng Văn. Truyền thuyết này cũng được áp dụng cho chùa Bà Ngô, một ngôi chùa ở cạnh chùa Bà Nành. (chi tiết, xin xem: chùa Bà Ngô)